Graph / Independent set (Bibtex)

P25: Enumeration of all maximal independent sets in a chordal graph

Input:

A graph $G=(V,E)$.

Output:

All maximal independent sets in $G$.

Complexity:

$O(|V||E|\mu)$ total time.

Comment:

$\mu$ is the number of maximal independent sets of $G$. This algorithm can also enumerate all the maximal cliques.

Reference:

[Tsukiyama1977a] (Bibtex)

P380: Enumeration of all maximal independent sets in a claw-free graph

Input:

A claw-free graph $G$.

Output:

All maximal independent sets in $G$.

Complexity:

Comment:

Reference:

[Minty1980] (Bibtex)

P375: Enumeration of all maximal independent sets in an undirected graph

Input:

A graph $G$.

Output:

All maximal independent sets in $G$ in lexicographically.

Complexity:

Comment:

Reference:

[Loukakis1981] (Bibtex)

P366: Enumeration of all maximal independent sets in an interval graph

Input:

An interval graph $G = (V, E)$.

Output:

All maximal independent sets in $G$.

Complexity:

$O(|V|^2 + \beta)$ total time.

Comment:

$\beta$ is the sum of the vertices in all maximal independent sets of $G$.

Reference:

[Leung1984] (Bibtex)

P367: Enumeration of all maximal independent sets in a circular-arc graph

Input:

A circular-arc graph $G = (V, E)$.

Output:

All maximal independent sets in $G$.

Complexity:

$O(|V|^2 + \beta)$ total time.

Comment:

$\beta$ is the sum of the vertices in all maximal independent sets of $G$.

Reference:

[Leung1984] (Bibtex)

P368: Enumeration of all maximal independent sets in a chordal graph

Input:

A chordal graph $G = (V, E)$.

Output:

All maximal independent sets in $G$.

Complexity:

$O((|V| + |E|)N)$ total time.

Comment:

$N$ is the number of solutions.

Reference:

[Leung1984] (Bibtex)

P29: Enumeration of all maximal independent sets in a graph

Input:

A graph $G=(V,E)$.

Output:

All maximal independent sets included in $G$.

Complexity:

$O(n(m+n\log C))=O(n^3)$ delay and exponential space.

Comment:

$C$: total number of maximal independent sets, $n$: total number of vertices, and $m$: total number of edges. Is there no polynomial space and delay algorithm?

Reference:

[Johnson1988] (Bibtex)

P76: Enumeration of all maximum independent sets of a bipartite graph

Input:

A bipartite graph $B =(V, E)$.

Output:

All maximum independent sets of $B$.

Complexity:

$O(|V|^{2.5} + \gamma)$.

Comment:

$\gamma$ is the output size, that is the sum of the all solutions.

Reference:

[Kashiwabara1992] (Bibtex)

P334: Enumeration of all maximal independent sets on a tree in lexicographic order

Input:

A tree $T = (V, E)$.

Output:

All maximal independent sets on $T$ in lexicographic order.

Complexity:

$O(|V|^2)$ delay with $O(|V|)$ space.

Comment:

Reference:

[Chang1994a] (Bibtex)

P305: Enumeration of all maximum independent set of a graph

Input:

A graph $G = (V, E)$.

Output:

All maximum independent set of $G$.

Complexity:

$O(2^{0.114|E|})$ total time and polynomial space.

Comment:

Reference:

[Beigel1999] (Bibtex)

P306: Enumeration of all maximum independent set of a graph

Input:

A graph $G = (V, E)$ with maximum degree 3.

Output:

All maximum independent set of $G$.

Complexity:

$O(2^{0.171|V|})$ total time and polynomial space.

Comment:

Reference:

[Beigel1999] (Bibtex)

P307: Enumeration of all maximum independent set of a graph

Input:

A graph $G = (V, E)$ with maximum degree 4.

Output:

All maximum independent set of $G$.

Complexity:

$O(2^{0.228|V|})$ total time and polynomial space.

Comment:

Reference:

[Beigel1999] (Bibtex)

P308: Enumeration of all maximum independent set of a graph

Input:

A graph $G = (V, E)$.

Output:

All maximum independent set of $G$.

Complexity:

$O(2^{0.290|V|})$ total time and polynomial space.

Comment:

Reference:

[Beigel1999] (Bibtex)

P291: Enumeration of all maximal independent sets of a graph

Input:

A graph $G = (V, E)$ and a position integer $k$.

Output:

Enumeration of all maximal independent sets with at most size $k$ of $G$.

Complexity:

$O(3^{4k-|V|} 4^{|V|-3k})$ total time.

Comment:

Reference:

[Eppstein2003a] (Bibtex)

P282: Enumeration of all independent sets in a chordal graph

Input:

A chordal graph $G = (V, E)$.

Output:

All independent sets in $G$.

Complexity:

Constant time per solution on average after $O(|V| + |E|)$ time for preprocessing.

Comment:

Reference:

[Okamoto2005a] (Bibtex)

P283: Enumeration of all independent sets of size $k$ in a chordal graph

Input:

A chordal graph $G = (V, E)$ and a positive integer $k$.

Output:

All independent sets of size $k$ in $G$.

Complexity:

Constant time per solution on average after $O((|V| + |E|)|V|^2)$ time for preprocessing.

Comment:

Reference:

[Okamoto2005a] (Bibtex)

P284: Enumeration of all maximum independent sets in a chordal graph

Input:

A chordal graph $G = (V, E)$.

Output:

All maximum independent sets in $G$.

Complexity:

Constant time per solution on average after $O((|V| + |E|)|V|^2)$ time for preprocessing.

Comment:

Reference:

[Okamoto2005a] (Bibtex)

P26: Enumeration of all independent sets in an input chordal graph

Input:

A chordal graph $G=(V,E)$.

Output:

All independent sets in $G$.

Complexity:

$O(1)$ delay and $O(|V|(|V|+|E|))$ time and space for preprocessing.

Comment:

Counting all independent sets in an input chordal graph needs $O(n+m)$ time.

Reference:

[Okamoto2008] (Bibtex)

P27: Enumeration of all maximum independent sets in an input chordal graph

Input:

A chordal graph $G=(V,E)$.

Output:

All maximum independent sets in $G$.

Complexity:

$O(1)$ delay and $O(|V|(|V|+|E|))$ time and space for preprocessing.

Comment:

Counting all maximum independent sets in an input chordal graph needs $O(n+m)$ time.

Reference:

[Okamoto2008] (Bibtex)

P28: Enumeration of all independent sets with $k$ vertices in an input chordal graph

Input:

A chordal graph $G=(V,E)$ and an integer $k$.

Output:

All maximum independent sets with $k$ vertices in $G$.

Complexity:

$O(1)$ delay and $O(k|V|(|V|+|E|))$ time and space for preprocessing.

Comment:

The number of independent sets with $k$ vertices in an input chordal graph needs $O(k^2(|V|+|E|))$ time.

Reference:

[Okamoto2008] (Bibtex)